import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public static TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        TreeNode node=new TreeNode(key);
        //若该搜索树为空，则直接作为根节点；
        if (root==null){
            root=node;
            return true;
        }

        TreeNode cur=root;
        TreeNode parent=null;

        while(cur!=null){
            if (cur.key<key){
                parent = cur;
                cur=cur.right;
            }else if(cur.key>key){
                parent = cur;
                cur=cur.left;
            }else{
                //重复
                return false;
            }
        }

        if (parent.key>key){
            parent.left=node;
            return true;
        }else{
            parent.right=node;
            return true;
        }

    }

    public TreeNode prev;
    public TreeNode cur;
    //二叉搜索树转双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        Convert(pRootOfTree.left);
        if(prev==null){
            cur=pRootOfTree;
            prev=pRootOfTree;
        }else{
            prev.right=pRootOfTree;
            pRootOfTree.left = prev;
            prev = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return cur;
    }

    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur =root;
        while(cur!=null){
            if (cur.key<key){
                cur=cur.right;
            }else if(cur.key>key){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        return null;
    }

    //删除key的值
    public boolean remove(int key) {
        TreeNode cur =root;
        TreeNode parent=null;
        while(cur!=null){
            if (cur.key>key){
                parent=cur;
                cur=cur.left;
            }else if (cur.key<key){
                parent=cur;
                cur=cur.right;
            }else{
                removeNode(parent,cur);
                return true;
            }
        }
        return false;
    }

    public void removeNode(TreeNode parent,TreeNode cur){
        if (cur.left==null){//左子树为空
            if (cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if (cur.right==null){//右子树为空
            if (cur==root){
                root=cur.left;
            }else if (cur==parent.left){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{//左右子树都不为空 右子树的最小值代替
            TreeNode targetp=cur;
            TreeNode target=cur.right;
            while(target!=null){
                targetp=target;
                target=target.left;
            }
            cur.key=target.key;
            //删除原本数值
            if (targetp.left==target){
                targetp.left=target.left;
            }else{
                targetp.right=target.right;
            }
        }
    }

    public void prevOreder(TreeNode root){
        if (root==null){
            return;
        }
        prevOreder(root.left);
        System.out.print(root.key+" ");
        prevOreder(root.right);
    }

}